import random

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

import matplotlib

# 设置matplotlib的字体
matplotlib.rcParams['font.sans-serif'] = ['SimHei']  # 指定默认字体为黑体
matplotlib.rcParams['axes.unicode_minus'] = False  # 解决保存图像时负号'-'显示为方块的问题

def generate_city_graph(n, show_img):
    """
    :param show_img: 是否显示图片
    :param n:代表有多少个城市。
    :return: city_ids表示各个城市的编号，customer表示各个城市客户数量，time_matrix记录了各个城市之间的运输时间。
    """
    # 生成城市编号向量
    city_ids = np.arange(0, n) #从0开始

    # 生成随机客户数量
    customer = np.random.randint(3, 20, size=n)

    # 生成一个完全图
    G = nx.complete_graph(n)

    # 生成时间矩阵
    time_matrix = np.full((n, n), -1)
    for i in range(n):
        for j in range(i + 1, n):
            time_matrix[i][j] = time_matrix[j][i] = np.random.randint(3, 20)

    if show_img:
        # 使用 networkx 绘制图 G
        plt.figure(figsize=(5, 5))  # 设置图形的大小

        # 为图 G 设置布局，这里使用 spring_layout 布局
        pos = nx.spring_layout(G)

        # 绘制节点，并在节点上显示城市编号和人口数量
        nx.draw_networkx_nodes(G, pos, node_size=700, node_color='skyblue')
        nx.draw_networkx_labels(G, pos, labels={i: f"{city_ids[i]} ({customer[i]})" for i in range(n)})

        # 绘制边，并在边上显示距离
        edge_labels = {(i, j): time_matrix[i, j] for i in range(n) for j in range(i + 1, n) if
                       time_matrix[i, j] != -1}
        nx.draw_networkx_edges(G, pos, edge_color='gray', width=2)
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color='red')

        plt.axis('off')  # 关闭坐标轴
        plt.show()  # 显示图形

    return city_ids, customer, time_matrix, G


def initialize_population_version2(cities, customers, time_matrix, N):
    """
    混合策略初始化。0.9随机初始化，0.1贪婪初始化。

    参数：
    - cities: 所有城市的编号 (np.ndarray)，假设第一个城市(编号为0)是起点和终点。
    - N: 种群数量，生成 N 个解。

    返回：
    - population: N 个解的列表，每个解是一个城市的访问顺序。
    """
    population = []

    sj_n = int(N*0.5) #随机初始化的数量

    tl_n = N - sj_n #贪婪初始化的数量

    for _ in range(sj_n):
        # 生成一个随机的城市顺序（去掉起点）
        order = np.random.permutation(cities[1:])

        # 将起点添加到顺序的开头，并加上终点（即起点）
        solution = np.insert(order, 0, cities[0])  # 起点在前
        solution = np.append(solution, cities[0])  # 终点为起点

        population.append(solution.tolist())

    weight_list = [i/(tl_n+1) for i in range(1,tl_n+1)] #权重列表

    # 贪婪初始化
    for weight in weight_list:
        current_city = 0  # 当前所在城市的编号
        this_path = [0]  # 本次路径，从起点开始
        city_remains = list(cities[1:])  # 剩余未访问的城市

        while len(city_remains) > 0:
            # 计算目标值 aim = weight * time - (1 - weight) * customers
            aims = [
                weight * time_matrix[current_city][next_city] -
                (1 - weight) * customers[next_city]
                for next_city in city_remains
            ]

            # 选择 aim 最小的城市作为下一个城市
            min_index = np.argmin(aims)
            next_city = city_remains[min_index]

            # 更新路径和当前城市
            this_path.append(next_city)
            current_city = next_city
            city_remains.remove(next_city)

        # 最后添加回起点
        this_path.append(cities[0])
        population.append(this_path)

    return population


def initialize_population(cities, N):
    """
    初始化种群，生成 N 个可能的旅行商解。每个解是一个访问顺序。

    参数：
    - cities: 所有城市的编号 (np.ndarray)，假设第一个城市(编号为0)是起点和终点。
    - N: 种群数量，生成 N 个解。

    返回：
    - population: N 个解的列表，每个解是一个城市的访问顺序。
    """
    population = []

    for _ in range(N):
        # 生成一个随机的城市顺序（去掉起点）
        order = np.random.permutation(cities[1:])

        # 将起点添加到顺序的开头，并加上终点（即起点）
        solution = np.insert(order, 0, cities[0])  # 起点在前
        solution = np.append(solution, cities[0])  # 终点为起点

        population.append(solution.tolist())

    return population


def calculate_fitness(population, customer, time_matrix):
    """
    计算每个基因在旅行商问题中的表现，基于平均每个人等待时间和总运输费用。

    参数：
    - population: 访问顺序（基因）的列表，包含多个个体，每个个体是城市访问的顺序。
    - customer: 各个城市的人口数量，比如customer[0]表示第一个城市有多少客户，其中0是城市的编号。
    - time_matrix: 城市间的时间矩阵。

    返回：
    - fitness_values: 每个基因在两个目标上的表现，包括平均每个人等待时间和总运输费用。
    """

    fitness_values = [] #其中每个元素是对应基因在两个目标上的表现 [平均等待时间，总运费]

    # 遍历每个个体（基因）
    for gene in population:
        total_travel_time = 0  # 该“基因”对应的从头到尾运输总时间，用来计算运费。

        current_time = 0 #当前已经花了多少时间。
        last_city = None #上一个城市的编号。

        cus_and_time=[] #记录各组的人等待了多少时间，其中的每个元素是 [人数，等待时间]，比如[10,33]表示有10个人等待了33单位的时间。

        for city in gene[:-1]: #city 是当前所在城市的编号。
            if last_city is None: #表明当前是第一个城市
                # 第一个城市，也就是起点，这里客户平均等待时间为在该城市卸货时间的一半。
                cus_and_time.append([customer[city],customer[city]/2])
                current_time += customer[city] #在该城市卸货花了那么多时间
                last_city = city
            else: #当前不是第一个城市
                current_time += time_matrix[last_city][city] #把路上花的时间计算进来。
                total_travel_time += time_matrix[last_city][city] #更新运输的总时间。

                # 这里客户平均等待时间为在该城市卸货时间的一半加上current_time。
                cus_and_time.append([customer[city], customer[city] / 2 + current_time])
                current_time += customer[city] #在该城市卸货花了那么多时间
                last_city = city

        #还要计算从最后一个城市返回起点的运输时间
        total_travel_time += time_matrix[last_city][0]  # 更新运输的总时间。

        all_time = 0
        all_people = 0

        for item in cus_and_time:
            all_people += item[0]
            all_time += item[1]*item[0]

        average_waiting_time = all_time/all_people
        all_cost = total_travel_time #总运费

        fitness_values.append([average_waiting_time,all_cost])

    return fitness_values


def non_dominated_sort(population, objectives):
    """
    对种群进行非支配排序，根据目标值排序并分配非支配层次。

    参数：
    - population: 各个基因的列表，每个基因是一个访问顺序。
    - objectives: 各个基因对应的目标值，格式为每个基因的[目标1, 目标2]值。

    返回：
    - fronts: 一个列表，每个元素是一个非支配层次的基因列表。最后得到的结果大体上是上层比下层更好，但是并不是绝对的上层支配下层。
    """
    # 初始化支配计数和支配集合
    domination_count = np.zeros(len(population), dtype=int)  # 每个个体被支配的数量
    dominated_set = [[] for _ in range(len(population))]  # 每个个体支配的个体集合
    fronts = [[]]  # 存储非支配层次的列表，最初只有第一层

    # 计算每个个体的支配关系
    for i in range(len(population)):
        for j in range(len(population)):
            if i != j:
                # 如果个体i支配个体j
                if dominates(objectives[i], objectives[j]):
                    dominated_set[i].append(j)  # i 支配 j
                # 如果个体j支配个体i
                elif dominates(objectives[j], objectives[i]):
                    domination_count[i] += 1  # i 被 j 支配

        # 如果i个体不被任何个体支配，则加入最优层
        if domination_count[i] == 0:
            fronts[0].append(i)

    # 分配剩余的非支配层次
    current_front = 0
    while len(fronts[current_front]) > 0:  #fronts[current_front]>0就表明这一层还有元素。
        next_front = []
        for i in fronts[current_front]:    #假设 current_front=0 ，那这里就是遍历0层的全部基因。
            for j in dominated_set[i]:     #遍历该基因支配的基因
                domination_count[j] -= 1   #让这个被支配基因的被支配数量减一
                if domination_count[j] == 0: # 这里就是说 i是第 n层的基因，j是i支配的某一个基因。那么除了i支配j以外没有别的支配j,
                                             # 那么j就可以放到 i 的下一层。
                    next_front.append(j)

        current_front += 1
        fronts.append(next_front)

    # 删除空层次
    fronts = [front for front in fronts if len(front) > 0]

    return fronts


def dominates(obj1, obj2):
    """
    判断目标值 obj1 是否支配目标值 obj2。
    支配关系：obj1 在所有目标上不劣于 obj2，且至少在一个目标上优于 obj2。
    这里是值越小就越优秀。

    参数：
    - obj1: 个体1的目标值（列表或数组）
    - obj2: 个体2的目标值（列表或数组）

    返回：
    - True 如果 obj1 支配 obj2，否则 False。
    """
    return all(o1 <= o2 for o1, o2 in zip(obj1, obj2)) and any(o1 < o2 for o1, o2 in zip(obj1, obj2))


def crowding_distance(objectives):
    """
    计算NSGA-II算法中的拥挤度

    参数:
    - objectives: 形状为 (n_samples, n_objectives) 的目标值数组，表示每个基因的目标值。

    返回:
    - 拥挤度数组，形状为 (n_samples,) 的数组，表示每个解的拥挤度。
    """
    n_samples, n_objectives = objectives.shape
    crowding_distances = np.zeros(n_samples)  # 先把各个拥挤度初始化为0，

    for i in range(n_objectives):
        # 按目标值排序
        sorted_indices = np.argsort(objectives[:, i])      #选择第i个目标值进行计算
        #np.argsort 返回数组元素从小到大的排序索引。

        sorted_objectives = objectives[sorted_indices, i]

        # 计算每个解的拥挤度
        crowding_distances[sorted_indices[0]] = np.inf  # 最小值的拥挤度为无穷大
        crowding_distances[sorted_indices[-1]] = np.inf  # 最大值的拥挤度为无穷大

        for j in range(1, n_samples - 1):
            crowding_distances[sorted_indices[j]] += (sorted_objectives[j + 1] - sorted_objectives[j - 1]) / (
                        sorted_objectives[-1] - sorted_objectives[0]+0.0001)

    return crowding_distances


def crossover(parent1, parent2):
    """
    对旅行商问题的两个父代基因序列进行交叉操作。

    Args:
        parent1: List[int] - 第一个父代基因序列。
        parent2: List[int] - 第二个父代基因序列。

    Returns:
        child1, child2: Tuple[List[int], List[int]] - 两个子代基因序列。
    """
    assert parent1[0] == parent2[0], "两个父代的起点和终点必须相同。"
    start_city = parent1[0]  # 起始城市

    # 去掉起点和终点，只保留核心城市序列
    p1_core = parent1[1:-1]
    p2_core = parent2[1:-1]
    length = len(p1_core)

    # 随机选择两个交叉点
    point1, point2 = sorted(random.sample(range(length), 2))

    # 初始化子代序列（使用 None 占位）
    child1_core = [None] * length
    child2_core = [None] * length

    # 将父代的交叉区域复制到对应子代中
    child1_core[point1:point2] = p1_core[point1:point2]
    child2_core[point1:point2] = p2_core[point1:point2]

    # 填充子代的其余部分，确保没有重复且覆盖所有城市
    def fill_rest(child, parent_segment, parent):
        """
        填充子代中剩余的基因，确保完整性和合法性。

        Args:
            child: List[Optional[int]] - 当前子代基因序列。
            parent_segment: List[int] - 交叉区域的基因片段。
            parent: List[int] - 另一个父代的核心基因序列。
        """
        for gene in parent:  # 遍历另一个父代的基因
            if gene not in parent_segment:  # 如果基因不在交叉区域
                for i in range(length):
                    if child[i] is None:  # 找到第一个空位填入基因
                        child[i] = gene
                        break

    # 分别填充两个子代
    fill_rest(child1_core, child1_core[point1:point2], p2_core)
    fill_rest(child2_core, child2_core[point1:point2], p1_core)

    # 将起点和终点加回子代序列
    child1 = [start_city] + child1_core + [start_city]
    child2 = [start_city] + child2_core + [start_city]

    return child1, child2

def mutation(gene):
    """
    对旅行商问题的基因进行变异，随机交换两个非起点城市的位置。

    Args:
        gene: List[int] - 输入的基因序列，包含起点和终点城市。

    Returns:
        mutated_gene: List[int] - 变异后的基因序列。
    """
    assert len(gene) > 3, "基因长度必须大于3，确保起点、终点和至少两个中间城市。"
    assert gene[0] == gene[-1], "基因的起点和终点必须相同。"

    # 复制原始基因以进行变异
    mutated_gene = gene[:]

    # 随机选择两个非起点城市的索引进行交换
    core_indices = range(1, len(mutated_gene) - 1)  # 中间城市的索引范围
    index1, index2 = random.sample(core_indices, 2)  # 随机选择两个不同的索引

    # 交换选中的城市
    temp1,temp2 = mutated_gene[index1], mutated_gene[index2]

    mutated_gene[index1], mutated_gene[index2] = temp2,temp1

    return mutated_gene

def crossover_and_mutation(genes):
    """
    对输入的基因进行交叉和变异操作。

    Args:
        genes: List[List[int]] - 一个基因列表，每个基因是一个旅行商问题的路径。
                                 假设列表的长度为偶数。

    Returns:
        List[List[int]] - 包含交叉结果和变异结果的所有基因。
    """
    assert len(genes) % 2 == 0, "基因列表的长度必须是偶数，确保可以两两配对。"

    # 用于存储交叉和变异后的新基因
    new_genes = []

    # === 交叉操作 ===
    # 将基因分成两半进行两两配对
    half = len(genes) // 2
    parents1 = genes[:half]
    parents2 = genes[half:]

    # 对每对父代基因进行交叉操作
    for parent1, parent2 in zip(parents1, parents2):
        child1, child2 = crossover(parent1, parent2)
        new_genes.extend([child1, child2])  # 将交叉后的两个子代加入列表

    # === 变异操作 ===
    mutated_genes = [mutation(gene) for gene in genes]  # 对每个父代进行变异

    # 将交叉结果和变异结果合并
    result = new_genes + mutated_genes

    return result

def select_best_genes(genes, fitness,fronts, n):
    """
    选择最优秀的 n 个基因，依据非支配排序和拥挤距离。

    Args:
        genes: List[List[int]] - 所有基因列表。
        fitness: List[List[float]] - 每个基因的目标值列表，形状为 (len(genes), 2)。
        fronts: 是多个层次，每层是基因的索引列表
        n: int - 需要选择的基因数量。

    Returns:
        List[List[int]] - 选择的最优秀基因列表。
    """

    # === 2. 按非支配层次优先选择 ===
    selected_genes = []
    selected_fitness = []

    for front in fronts:
        if len(selected_genes) + len(front) <= n:
            # 如果当前层的基因全选不会超过 n，则全部加入
            selected_genes.extend([genes[i] for i in front])
            selected_fitness.extend([fitness[i] for i in front])
        else:
            # 如果当前层加入后会超过 n，使用拥挤度选择
            all_fitness = np.array(fitness)
            crowding_distances = crowding_distance(all_fitness)

            # 获取当前层基因及其拥挤度
            current_front_indices = np.array(front)
            current_front_distances = crowding_distances[current_front_indices]

            # 按拥挤度从大到小排序当前层基因
            sorted_indices = np.argsort(-current_front_distances)  # 从大到小排序
            sorted_front = current_front_indices[sorted_indices]

            # 选择前 n 个基因
            remaining_slots = n - len(selected_genes)
            selected_genes.extend([genes[i] for i in sorted_front[:remaining_slots]])
            selected_fitness.extend([fitness[i] for i in sorted_front[:remaining_slots]])
            break  # 已经选满，结束

    return selected_genes

def plot_subgraphs(avg_wait_times, transport_costs):
    """
    绘制两个子图，横轴为迭代次数，纵轴分别为平均等待时间和运输费用。

    :param avg_wait_times: 列表，包含每次迭代的平均等待时间
    :param transport_costs: 列表，包含每次迭代的运输费用
    """
    # 检查两个列表长度是否一致
    if len(avg_wait_times) != len(transport_costs):
        raise ValueError("平均等待时间和运输费用的迭代次数必须相同")

    # 生成迭代次数作为横轴的值
    iterations = np.arange(1, len(avg_wait_times) + 1)

    # 创建一个图形和两个子图
    fig, (ax1, ax2) = plt.subplots(2, 1, figsize=(10, 8))

    # 第一个子图：平均等待时间
    ax1.plot(iterations, avg_wait_times, 'r-', label='Average Waiting Time')
    ax1.set_ylabel('平均等待时间')
    ax1.grid(True)

    # 第二个子图：运输费用
    ax2.plot(iterations, transport_costs, 'b-', label='Transport Costs')
    ax2.set_xlabel('迭代次数')
    ax2.set_ylabel('运输费用')
    ax2.grid(True)

    # 调整子图间距
    plt.tight_layout()

    # 显示图形
    plt.show()

    print(f'平均等待时间，初始值{avg_wait_times[0]},最终值{avg_wait_times[-1]},优化幅度：{1-avg_wait_times[-1]/avg_wait_times[0]}')
    print(
        f'运费，初始值{transport_costs[0]},最终值{transport_costs[-1]},优化幅度：{1-transport_costs[-1] / transport_costs[0]}')

def are_nested_lists_equal(list1, list2):
    # 检查两个列表的长度是否相同
    if len(list1) != len(list2):
        return False

    # 检查列表中的每个元素
    for elem1, elem2 in zip(list1, list2):
        # 如果元素是列表，递归地检查是否相等
        if isinstance(elem1, list) and isinstance(elem2, list):
            if not are_nested_lists_equal(elem1, elem2):
                return False
        # 如果元素不是列表，直接比较它们
        elif elem1 != elem2:
            return False
    return True

if __name__ == '__main__':
    pass
    #使用示例 1 生成一个图结构 ===========================================================================================
    ids,pop,dis,G=generate_city_graph(n=5,show_img=True)
    print('城市编号:',ids)
    print('城市客户数量:', pop)
    print('时间矩阵:\n',dis)

    # 示例用法 2 初始化种群 =============================================================================================
    # cities = np.array([0, 1, 2, 3, 4])  # 假设城市0为起点和终点
    # N = 2  # 种群数量
    # population = initialize_population(cities, N)
    # print("初始化的随机解为：",population)

    # 示例用法 3 计算各个基因的表现值 ======================================================================================

    # ids, cus, dis, G = generate_city_graph(n=20, show_img=False)
    #
    # print('城市编号:',ids)
    # print('城市客户数量:', cus)
    # print('距离矩阵:\n',dis)
    # print('\n')
    #
    #
    # population = initialize_population(ids ,N = 20)
    #
    # r=calculate_fitness(population,cus,dis)
    #
    # for i in range(len(population)):
    #     print(f'基因{i}{population[i]}的表现值：{r[i]},第一项是客户平均等待时间，第二项是运输成本。')
    # print('\n')
    #
    #
    # # 示例用法 4 非支配排序 (这里会用到上面的示例3的内容)=======================================================================
    #
    # fronts = non_dominated_sort(population, r)
    #
    # # 输出每个非支配层次
    # for i, front in enumerate(fronts):
    #     print(f"级别{i + 1}: {front}")
    # print('\n')
    # # 示例用法 5 计算拥挤度 (这里会用到上面的示例3的内容)=======================================================================
    #
    # result = crowding_distance(np.array(r))
    #
    # for i in range(len(result)):
    #     print(f'基因{i}的拥挤度为：{result[i]}')
    # print('\n')

